Thực đơn
Giải_thuật_Euclid
Giải thuật Euclid gồm một dãy các bước mà trong đó, đầu ra của mỗi bước là đầu vào của bước kế tiếp. Gọi k là số nguyên dùng để đếm số bước của thuật toán, bắt đầu từ số không (khi đó bước đầu tiên tương ứng với k = 0, bước tiếp theo là k = 1,...)
Mỗi bước bắt đầu với hai số dư không âm rk−1 và rk−2. Vì thuật toán giúp đảm bảo số dư luôn giảm dần theo từng bước nên rk−1 nhỏ hơn rk−2. Mục tiêu của bước thứ k là tìm thương qk và số dư rk thỏa mãn phương trình
r k − 2 = q k r k − 1 + r k {\displaystyle r_{k-2}=q_{k}r_{k-1}+r_{k}}và 0 ≤ rk < rk−1. Nói cách khác, từ số lớn hơn rk−2, trừ đi bội của số nhỏ hơn rk−1 đến khi phần dư rk nhỏ hơn rk−1.
Ở bước đầu tiên (k = 0), số dư r−2 và r−1 bằng a và b, hai số cần tìm ƯCLN. Đến bước kế tiếp (k = 1), hai số dư lần lượt bằng b và số dư r0 ở bước đầu tiên,... Do đó, thuật toán có thể được viết thành một dãy các phương trình
a = q 0 b + r 0 b = q 1 r 0 + r 1 r 0 = q 2 r 1 + r 2 r 1 = q 3 r 2 + r 3 ⋮ {\displaystyle {\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\r_{0}&=q_{2}r_{1}+r_{2}\\r_{1}&=q_{3}r_{2}+r_{3}\\&\,\,\,\vdots \end{aligned}}}Nếu a nhỏ hơn b thì thuật toán đảo ngược vị trí của hai số. Chẳng hạn, nếu a < b thì thương q0 bằng không và số dư r0 bằng a. Do đó, rk luôn nhỏ hơn rk−1 với mọi k ≥ 0.
Vì các số dư luôn giảm dần theo từng bước nhưng không thể là số âm nên số dư sau cùng rN phải bằng không và thuật toán dừng lại tại đó.[13] Số dư khác không cuối cùng rN−1 chính là ước chung lớn nhất của a và b. Số N không thể là vô hạn vì chỉ có một số lượng hữu hạn các số nguyên dương nằm giữa số dư ban đầu r0 và số không.
Tính đúng đắn của giải thuật Euclid có thể được chứng minh qua hai bước lập luận.[14] Bước thứ nhất, cần chứng minh số dư khác không cuối cùng rN−1 chia được cả a và b. Vì rN−1 là một ước chung nên nó phải nhỏ hơn hoặc bằng với ước chung lớn nhất g. Bước thứ hai, cần chứng minh rằng bất kỳ ước chung nào của a và b, trong đó có g cần phải chia được rN−1; từ đó, g phải nhỏ hơn hoặc bằng rN−1. Hai kết luận trên là mâu thuẫn trừ khi rN−1 = g.
Để chứng tỏ rN−1 chia được cả a và b, cần biết rN−1 chia được số dư liền trước rN−2:
rN−2 = qN rN−1vì số dư cuối cùng rN bằng không. rN−1 cũng chia được số dư rN−3:
rN−3 = qN−1 rN−2 + rN−1vì nó chia được cả hai số hạng trong vế phải của phương trình. Chứng minh tương tự, rN−1 cũng chia được tất cả số dư liền trước nó kể cả a và b. Không có số dư liền trước rN−2, rN−3,... chia bởi a và b cho số dư bằng không. Vì rN−1 là ước chung của a và b nên rN−1 ≤ g.
Trong bước thứ hai, một số tự nhiên c bất kỳ chia được cả a và b (là ước chung của a và b) cũng chia được số dư rk. Theo định nghĩa thì a và b có thể được viết thành bội của c: a = mc và b = nc với m và n là các số tự nhiên. Ta có r0 = a − q0b = mc − q0nc = (m − q0n)c nên c là một ước của số dư ban đầu r0. Chứng minh như bước thứ nhất, ta thấy c cũng là ước của các số dư liền sau r1, r2,... Từ đó, ước chung lớn nhất g là ước của rN−1 hay g ≤ rN−1. Kết hợp hai kết luận thu được, ta có g = rN−1. Vậy g là ước chung lớn nhất của tất cả cặp số liền sau:[15][16]
g = ƯCLN(a, b) = ƯCLN(b, r0) = ƯCLN(r0, r1) = … = ƯCLN(rN−2, rN−1) = rN−1.Áp dụng giải thuật Euclid để tính ƯCLN của a = 1071 và b = 462. Đầu tiên, ta trừ bội của 462 từ 1071 thì được thương q0 = 2 và số dư là 147:
1071 = 2 × 462 + 147.Tiếp tục trừ bội của 147 từ 462 thì được thương q1 = 3 và số dư là 21:
462 = 3 × 147 + 21.Tiếp tục trừ bội của 21 từ 147 thì được thương q2 = 7 và số dư là 0:
147 = 7 × 21 + 0.Vì số dư cuối cùng bằng 0 nên thuật toán kết thúc với 21 là ƯCLN của 1071 và 462, bằng với ƯCLN có được từ phép phân tích ra thừa số nguyên tố như trên. Các bước được tóm tắt thành bảng sau:
| Bước k | Phương trình | Thương và số dư |
|---|---|---|
| 0 | 1071 = q0 462 + r0 | q0 = 2 và r0 = 147 |
| 1 | 462 = q1 147 + r1 | q1 = 3 và r1 = 21 |
| 2 | 147 = q2 21 + r2 | q2 = 7 và r2 = 0; kết thúc |
Giải thuật Euclid có thể được minh họa dựa vào bài toán hình chữ nhật tương tự như trên.[17] Giả sử ta cần dùng hình vuông để lấp đầy một hình chữ nhật có kích thước là a × b với a là số lớn hơn. Đầu tiên, ta đặt các hình vuông b × b lên trên đó thì còn lại phần hình trống là một hình chữ nhật b × r0 với r0 < b. Tiếp theo, ta đặt các hình vuông r0 × r0 lên phần hình trống đó thì còn lại phần hình trống thứ hai r1 × r0 mà ta cần phải đặt lên đó các hình vuông r1 × r1,... Toàn bộ quá trình chỉ kết thúc khi không còn phần hình trống nào, và khi đó, độ dài cạnh hình vuông nhỏ nhất chính là ƯCLN của độ dài hai cạnh hình chữ nhật ban đầu. Chẳng hạn, hình vuông nhỏ nhất trong hình bên là 21 × 21 (màu đỏ), và 21 là ƯCLN của 1071 và 462, độ dài hai cạnh của hình chữ nhật ban đầu (màu xanh lá).
Tại mỗi bước k, giải thuật Euclid tính một thương qk và số dư rk từ hai số rk−1 và rk−2:
rk−2 = qk rk−1 + rktrong đó rk không âm và nhỏ hơn giá trị tuyệt đối của rk−1. Định lý làm nền tảng cho phép chia có dư cho thấy luôn tồn tại duy nhất một thương và số dư như vậy.[18]
Trong dạng ban đầu của giải thuật, thương và số dư được tìm bằng cách lặp lại phép trừ, nghĩa là trừ rk−1 từ rk−2 và lặp lại đến khi phần dư rk nhỏ hơn rk−1, sau đó hoán đổi chúng cho nhau rồi lại lặp lại quá trình này. Phép chia có dư hiệu quả hơn nhiều khi giảm đi số bước giữa hai hoán đổi còn một bước duy nhất. Hơn nữa, ta còn có thể thay phép chia có dư bằng phép toán modulo, vốn chỉ cho kết quả số dư. Như vậy, dạng lặp của giải thuật Euclid trở thành
rk = rk−2 mod rk−1.Giải thuật Euclid có thể được biểu diễn bằng mã giả. Chẳng hạn, dạng phép chia của nó có thể được lập trình thành[19]
function gcd(a, b) while b ≠ 0 t := b b := a mod b a := t return a
Ở đầu vòng lặp k, biến b mang giá trị số dư rk−1, trong khi biến a mang giá trị số dư liền trước rk−2. Bước b := a mod b giống với công thức đệ quy như trên rk ≡ rk−2 mod rk−1. Biến tạm thời t mang giá trị rk−1 khi tính số dư liền sau rk. Cuối vòng lặp, biến b mang giá trị rk, trong khi biến a mang giá trị số dư liền trước rk−1.
Trong dạng phép trừ (dạng ban đầu của thuật toán), bước b := a mod b được thay bằng phép trừ lặp lại.[20] Trái ngược với dạng phép chia cho phép đầu vào là một số nguyên bất kỳ, dạng phép trừ chỉ cho phép đầu vào là một số nguyên dương và dừng lại khi a = b:
function gcd(a, b) while a ≠ b if a > b a := a − b else b := b − a return a
Biến a và b luân phiên mang giá trị của các số dư liền trước rk−1 và rk−2. Giả sử a > b ở đầu một vòng lặp thì a bằng rk−2 vì rk−2 > rk−1. Trong vòng lặp, a được trừ đi bởi bội của số dư liền trước b đến khi a nhỏ hơn b, khi đó a trở thành số dư liền sau rk. Sau đó, b được trừ đi bởi bội của a đến khi nó nhỏ hơn a và phần còn lại trở thành số dư rk+1,...
Dạng đệ quy dựa trên tính chất ƯCLN của các cặp số dư liên tiếp là bằng nhau và điều kiện dừng lại là ƯCLN(rN−1, 0) = rN−1.[21]
function gcd(a, b) if b = 0 return a else return gcd(b, a mod b)
Sử dụng dạng này, ƯCLN(1071, 462) được tính từ ƯCLN(462, 1071 mod 462) = ƯCLN(462, 147). ƯCLN sau cùng được tính từ ƯCLN(147, 462 mod 147) = ƯCLN(147, 21), vốn được tính từ ƯCLN(21, 147 mod 21) = ƯCLN(21, 0) = 21.
Trong một dạng khác của giải thuật Euclid, thương thu được qua mỗi bước được tăng thêm 1 đơn vị nếu giá trị tuyệt đối của phần dư âm nhỏ hơn so với giá trị tuyệt đối của phần dư dương.[22][23] Điều kiện của phương trình
rk−2 = qk rk−1 + rklà |rk−1| > rk > 0. Tuy nhiên, có thể tính số dư âm ek bởi
rk−2 = (qk + 1) rk−1 + eknếu rk−1 > 0 hoặc
rk−2 = (qk − 1) rk−1 + eknếu rk−1 < 0.
Nếu thay rk bằng ek với |ek| < |rk| thì ta có một dạng khác của giải thuật Euclid sao cho trong mỗi bước,
|rk| ≤ |rk−1| / 2.Leopold Kronecker chứng minh được rằng dạng này tốn số bước ít nhất trong tất cả các dạng của giải thuật Euclid.[22][23] Tổng quát hơn, người ta chứng minh được rằng với mọi số đầu vào a và b, số bước tính ƯCLN là nhỏ nhất khi và chỉ khi qk được chọn sao cho | r k + 1 r k | < 1 φ ∼ 0 , 618 {\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0,618} với φ {\displaystyle \varphi } là tỷ lệ vàng.[24]
Thực đơn
Giải_thuật_EuclidLiên quan
Tài liệu tham khảo
WikiPedia: Giải_thuật_Euclid